package com.everyday.practice.algorithm;

/**
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        Integer[] arr=new Integer[5];
        arr[0]=10;
        arr[1]=2;
        arr[2]=31;
        arr[3]=22;
        arr[4]=1;
        QuickSort sort=new QuickSort();
        sort.sort(arr,0,4);
        System.out.println(arr);
    }

    public void sort(Integer[] arr,Integer start,Integer end){
        if (start<end){
            Integer sortIndex=sortIndex(arr,start,end);
            sort(arr,start,sortIndex-1);
            sort(arr,sortIndex+1,end);
        }
    }

    public Integer sortIndex(Integer[] arr,Integer start,Integer end){
        Integer temp=arr[start];
        while (start<end){
            while (start<end&&arr[end]>=temp){
                end--;
            }
            arr[start]=arr[end];
            while (start<end&&arr[start]<=temp){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=temp;
        return start;
    }
}
